<html>
  <head>
    <meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>K最近邻分类算法（KNN）分析及实现 | JIANG-HS</title>
<link rel="shortcut icon" href="https://JIANG-HS.github.io/favicon.ico?v=1600693149942">
<link href="https://cdn.jsdelivr.net/npm/remixicon@2.3.0/fonts/remixicon.css" rel="stylesheet">
<link rel="stylesheet" href="https://JIANG-HS.github.io/styles/main.css">
<link rel="alternate" type="application/atom+xml" title="K最近邻分类算法（KNN）分析及实现 | JIANG-HS - Atom Feed" href="https://JIANG-HS.github.io/atom.xml">
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Droid+Serif:400,700">


<script async src="https://www.googletagmanager.com/gtag/js?id=UA-xxxxxxxxx-x"></script>
<script>
  window.dataLayer = window.dataLayer || [];
  function gtag(){dataLayer.push(arguments);}
  gtag('js', new Date());

  gtag('config', 'UA-xxxxxxxxx-x');
</script>


    <meta name="description" content="一、KNN算法简介
K最近邻（KNN，K-NearestNeighbor）分类算法是数据挖掘分类技术中最简单的方法之一。所谓K最近邻，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的K个邻近值来代表。 K最近邻算法就是将数据集合中..." />
    <meta name="keywords" content="监督学习,分类算法,KNN,人工智能,机器学习" />
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.10.0/katex.min.css">
    <script src="https://cdn.bootcss.com/highlight.js/9.12.0/highlight.min.js"></script>
  </head>
  <body>
    <div class="main">
      <div class="main-content">
        <div class="site-header">
  <a href="https://JIANG-HS.github.io">
  <img class="avatar" src="https://JIANG-HS.github.io/images/avatar.png?v=1600693149942" alt="">
  </a>
  <h1 class="site-title">
    JIANG-HS
  </h1>
  <p class="site-description">
    姜还是老的辣
  </p>
  <div class="menu-container">
    
      
        <a href="/" class="menu">
          首页
        </a>
      
    
      
        <a href="/archives" class="menu">
          归档
        </a>
      
    
      
        <a href="/tags" class="menu">
          标签
        </a>
      
    
      
        <a href="/post/about" class="menu">
          关于
        </a>
      
    
  </div>
  <div class="social-container">
    
      
    
      
    
      
    
      
    
      
    
  </div>
</div>

        <div class="post-detail">
          <article class="post">
            <h2 class="post-title">
              K最近邻分类算法（KNN）分析及实现
            </h2>
            <div class="post-info">
              <span>
                2020-07-13
              </span>
              <span>
                9 min read
              </span>
              
                <a href="https://JIANG-HS.github.io/tag/1J0cdnH1y/" class="post-tag">
                  # 监督学习
                </a>
              
                <a href="https://JIANG-HS.github.io/tag/WAlsvxmAbk/" class="post-tag">
                  # 分类算法
                </a>
              
                <a href="https://JIANG-HS.github.io/tag/mABSccvvm8/" class="post-tag">
                  # KNN
                </a>
              
                <a href="https://JIANG-HS.github.io/tag/hPqZti1l1/" class="post-tag">
                  # 人工智能
                </a>
              
                <a href="https://JIANG-HS.github.io/tag/2ypiqV3K8b/" class="post-tag">
                  # 机器学习
                </a>
              
            </div>
            
            <div class="post-content-wrapper">
              <div class="post-content">
                <h1 id="一-knn算法简介">一、KNN算法简介</h1>
<p>K最近邻（KNN，K-NearestNeighbor）分类算法是数据挖掘分类技术中最简单的方法之一。<strong>所谓K最近邻，就是K个最近的邻居的意思</strong>，说的是每个样本都可以用它最接近的K个邻近值来代表。 K最近邻算法就是将数据集合中每一个记录进行分类的方法，是一个理论上比较成熟的方法，也是最简单的机器学习算法之一。<br>
<strong>优点：</strong></p>
<ul>
<li>所选择的邻居都是已经正确分类的对象</li>
<li>KNN算法本身比较简单，分类器不需要使用训练集进行训练，训练时间复杂度为0。本算法分类的复杂度与训练集中数据的个数成正比。</li>
<li>对于类域的交叉或重叠较多的待分类样本，KNN算法比其他方法跟合适。</li>
</ul>
<p><strong>缺点：</strong></p>
<ul>
<li>当样本分布不平衡时，很难做到正确分类</li>
<li>计算量较大，因为每次都要计算测试数据到全部数据的距离。</li>
</ul>
<h1 id="二-算法原理">二、算法原理</h1>
<p><img src="https://JIANG-HS.github.io/post-images/1594688558017.png" alt="" loading="lazy"><br>
如上图所示，图中的数据可以分为蓝色正方形和红色三角形两类，图中心的绿色圆点是待分类数据，下面我们通过K最近领法对绿色圆点进行分类：<br>
1.当k=3时，由图中实线圆内的数据可知：绿色圆点最近领的三个邻居中，一共有一个蓝色正方形和两个红色三角形，那么就可以将绿色圆点和红色三角形判定为一类。<br>
2.当k=5时，由图中虚线圆内的数据可知：绿色圆点最近领的五个邻居中，一共有三个蓝色正方形和两个红色三角形，那么就可以将绿色圆点和蓝色正方形判定为一类。<br>
至此，我们对KNN算法已经有了大概的了解。</p>
<h1 id="三-算法步骤">三、算法步骤</h1>
<h2 id="1初始化数据集">1.初始化数据集</h2>
<p>初始化训练集和测试集。训练集一般为两类或者多种类别的数据；测试集一般为一个数据。</p>
<h2 id="2计算距离">2.计算距离</h2>
<p>计算测试数据到其他所有数据的距离，并记录下来。<br>
常用到的距离计算公式如下：<br>
①欧几里得距离（欧氏距离）：d=<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msqrt><mrow><mo>(</mo><msub><mi>x</mi><mn>1</mn></msub><mo>−</mo><msub><mi>x</mi><mn>2</mn></msub><msup><mo>)</mo><mn>2</mn></msup><mo>+</mo><mo>(</mo><msub><mi>y</mi><mn>1</mn></msub><mo>−</mo><msub><mi>y</mi><mn>2</mn></msub><msup><mo>)</mo><mn>2</mn></msup></mrow></msqrt></mrow><annotation encoding="application/x-tex">\sqrt{(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.24em;vertical-align:-0.30499999999999994em;"></span><span class="mord sqrt"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.935em;"><span class="svg-align" style="top:-3.2em;"><span class="pstrut" style="height:3.2em;"></span><span class="mord" style="padding-left:1em;"><span class="mopen">(</span><span class="mord"><span class="mord mathdefault">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord"><span class="mord mathdefault">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose"><span class="mclose">)</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.740108em;"><span style="top:-2.9890000000000003em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mopen">(</span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.03588em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">1</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.03588em;">y</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.30110799999999993em;"><span style="top:-2.5500000000000003em;margin-left:-0.03588em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose"><span class="mclose">)</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.740108em;"><span style="top:-2.9890000000000003em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span></span></span></span></span></span></span></span></span></span></span><span style="top:-2.8950000000000005em;"><span class="pstrut" style="height:3.2em;"></span><span class="hide-tail" style="min-width:1.02em;height:1.28em;"><svg width='400em' height='1.28em' viewBox='0 0 400000 1296' preserveAspectRatio='xMinYMin slice'><path d='M263,681c0.7,0,18,39.7,52,119c34,79.3,68.167,
158.7,102.5,238c34.3,79.3,51.8,119.3,52.5,120c340,-704.7,510.7,-1060.3,512,-1067
c4.7,-7.3,11,-11,19,-11H40000v40H1012.3s-271.3,567,-271.3,567c-38.7,80.7,-84,
175,-136,283c-52,108,-89.167,185.3,-111.5,232c-22.3,46.7,-33.8,70.3,-34.5,71
c-4.7,4.7,-12.3,7,-23,7s-12,-1,-12,-1s-109,-253,-109,-253c-72.7,-168,-109.3,
-252,-110,-252c-10.7,8,-22,16.7,-34,26c-22,17.3,-33.3,26,-34,26s-26,-26,-26,-26
s76,-59,76,-59s76,-60,76,-60z M1001 80H40000v40H1012z'/></svg></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.30499999999999994em;"><span></span></span></span></span></span></span></span></span><br>
②曼哈顿距离<br>
③闵可夫斯基距离<br>
④切比雪夫距离<br>
⑤马氏距离<br>
⑥余弦相似度<br>
⑦皮尔逊相关系数<br>
⑧汉明距离<br>
⑨杰卡德相似系数<br>
⑩编辑距离<br>
⑪DTW 距离<br>
⑫KL 散度</p>
<h2 id="3寻找最近邻数据">3.寻找最近邻数据</h2>
<p>将所有距离进行升序排序，确定K值，最近的K个邻居即距离最短的K个数据。<br>
<strong>关于K值得选择问题：</strong></p>
<ul>
<li>K 值的选择会对算法的结果产生重大影响。</li>
<li>K值较小意味着只有与测试数据较近的训练实例才会对预测结果起作用，容易发生过拟合。</li>
<li>如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与测试数据较远的训练实例也会对预测起作用，使预测发生错误。</li>
<li>在实际应用中，K 值一般选择一个较小的数值，通常采用<strong>交叉验证</strong>的方法来选择最优的 K 值。随着训练实例数目趋向于无穷和 K=1 时，误差率不会超过贝叶斯误差率的2倍，如果K也趋向于无穷，则误差率趋向于贝叶斯误差率。（贝叶斯误差可以理解为最小误差）</li>
</ul>
<p><strong>三种交叉验证方法</strong>：</p>
<ul>
<li>Hold-Out： 随机从最初的样本中选出部分，形成交叉验证数据，而剩余的就当做训练数据。 一般来说，少于原本样本三分之一的数据被选做验证数据。常识来说，Holdout 验证并非一种交叉验证，因为数据并没有交叉使用。</li>
<li>K-foldcross-validation：K折交叉验证，初始采样分割成K个子样本，一个单独的子样本被保留作为验证模型的数据，其他K-1个样本用来训练。交叉验证重复K次，每个子样本验证一次，平均K次的结果或者使用其它结合方式，最终得到一个单一估测。这个方法的优势在于，同时重复运用随机产生的子样本进行训练和验证，每次的结果验证一次，10折交叉验证是最常用的。</li>
<li>Leave-One-Out Cross Validation：正如名称所建议， 留一验证(LOOCV)意指只使用原本样本中的一项来当做验证资料， 而剩余的则留下来当做训练资料。 这个步骤一直持续到每个样本都被当做一次验证资料。 事实上，这等同于 K-fold 交叉验证是一样的，其中K为原本样本个数。</li>
</ul>
<h2 id="4决策分类">4.决策分类</h2>
<p>明确K个邻居中所有数据类别的个数，将测试数据划分给个数最多的那一类。即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别。<br>
最常用的两种决策规则：</p>
<ul>
<li>多数表决法：多数表决法和我们日常生活中的投票表决是一样的，少数服从多数，是最常用的一种方法。</li>
<li>加权表决法：有些情况下会使用到加权表决法，比如投票的时候裁判投票的权重更大，而一般人的权重较小。所以在数据之间有权重的情况下，一般采用加权表决法。</li>
</ul>
<p><strong>图示说明（其中K=4）：</strong><br>
<img src="https://JIANG-HS.github.io/post-images/1594783091674.jpg" alt="" loading="lazy"></p>
<h1 id="四-python代码实现">四、python代码实现</h1>
<pre><code>import matplotlib.pyplot as plt
import matplotlib
from math import sqrt

#############################初始化数据集###################################
data_A = [[1,2],[3.2,4],[4,7],[5.2,3],[7,4.1]]#数据集A
data_B = [[2.2,5.5],[4.2,2],[5,5],[6.3,7]]#数据集B
test_data = [[4.5,4.5]]#测试集
len_A = len(data_A)
len_B = len(data_B)

############################计算距离并排序####################################
distance_A = []#与A类数据之间的距离
distance_B = []#与B类数据之间的距离
distance = []#全部距离
#计算距离（使用欧氏距离）
for i in range(len_A):
    d = sqrt((test_data[0][0]-data_A[i][0])**2+(test_data[0][1]-data_A[i][1])**2)
    distance_A.append(d)
for i in range(len_B):
    d = sqrt((test_data[0][0]-data_B[i][0])**2+(test_data[0][1]-data_B[i][1])**2)
    distance_B.append(d)
#由小到大排序（此处使用冒泡排序）
distance = distance_A + distance_B
for i in range(len(distance)-1):
    for j in range(len(distance)-i-1):
        if distance[j] &gt; distance[j+1]:
            distance[j],distance[j+1]=distance[j+1],distance[j]
print(&quot;距离所有A类数据的距离为：&quot;)
print(distance_A)
print(&quot;距离所有B类数据的距离为：&quot;)
print(distance_B)
print()
print(&quot;对所有的距离升序排序：&quot;)
print(distance)
print()

######################按K最近领对测试集进行分类##################################
K = 5#这里默认K值为5，也可以自行更改
number_A = 0
number_B = 0
#定义删除函数，避免对同一个数据重复计算
def delete(a,b,ls):
    for i in range(b):
        if ls[i]==a:
            ls.pop(i)
            break
#找出与测试数据最接近的K个点
for i in range(K):
    if distance[i] in distance_A:
        number_A += 1
        delete(distance[i],len(distance_A),distance_A)
        continue
    if distance[i] in distance_B:
        number_B += 1
        delete(distance[i],len(distance_B),distance_B)
        continue
print(&quot;最终结果：&quot;)
print(&quot;距离待测数据最近的K={:}个数据中，A类数据有{:}个，B类数据有{:}个&quot;.format(K,number_A,number_B))
if number_A &gt; number_B:
    print(&quot;所以K={:}时，待测数据划分为A类&quot;.format(K))
else:
    print(&quot;所以K={:}时，待测数据划分为B类&quot;.format(K))

#################################画图##########################################
matplotlib.rcParams['font.sans-serif'] = ['SimHei']
for i in range(len_A):#A类，用红色三角形表示
    if i!=len_A-1:
        plt.plot(data_A[i][0],data_A[i][1],'bo',marker='^',color='red')
    else:
        plt.plot(data_A[i][0],data_A[i][1],'bo',marker='^',label='A',color='r')
    #使用if..else...是为了避免在图形中重复出现多个标签
for i in range(len_B):#B类，用蓝色正方形表示
    if i!=len_B-1:
        plt.plot(data_B[i][0],data_B[i][1],'bo',marker='s',color='blue')
    else:
        plt.plot(data_B[i][0],data_B[i][1],'bo',marker='s',label='B',color='b')
plt.plot(test_data[0][0],test_data[0][1],'bo',label='待测数据',color='g')#测试集
plt.xlim(0,10)
plt.ylim(0,10)
plt.legend()
plt.show()
</code></pre>
<p><strong>图形：</strong><br>
<img src="https://JIANG-HS.github.io/post-images/1594783330527.png" alt="" loading="lazy"><br>
<strong>输出结果：</strong><br>
距离所有A类数据的距离为：<br>
[4.301162633521313, 1.3928388277184118, 2.5495097567963922, 1.6552945357246849, 2.5317977802344327]<br>
距离所有B类数据的距离为：<br>
[2.5079872407968904, 2.5179356624028344, 0.7071067811865476, 3.080584360149872]</p>
<p>对所有的距离升序排序：<br>
[0.7071067811865476, 1.3928388277184118, 1.6552945357246849, 2.5079872407968904, 2.5179356624028344, 2.5317977802344327, 2.5495097567963922, 3.080584360149872, 4.301162633521313]</p>
<p>最终结果：<br>
距离待测数据最近的K=5个数据中，A类数据有2个，B类数据有3个<br>
所以K=5时，待测数据划分为B类</p>

              </div>
              <div class="toc-container">
                <ul class="markdownIt-TOC">
<li><a href="#%E4%B8%80-knn%E7%AE%97%E6%B3%95%E7%AE%80%E4%BB%8B">一、KNN算法简介</a></li>
<li><a href="#%E4%BA%8C-%E7%AE%97%E6%B3%95%E5%8E%9F%E7%90%86">二、算法原理</a></li>
<li><a href="#%E4%B8%89-%E7%AE%97%E6%B3%95%E6%AD%A5%E9%AA%A4">三、算法步骤</a>
<ul>
<li><a href="#1%E5%88%9D%E5%A7%8B%E5%8C%96%E6%95%B0%E6%8D%AE%E9%9B%86">1.初始化数据集</a></li>
<li><a href="#2%E8%AE%A1%E7%AE%97%E8%B7%9D%E7%A6%BB">2.计算距离</a></li>
<li><a href="#3%E5%AF%BB%E6%89%BE%E6%9C%80%E8%BF%91%E9%82%BB%E6%95%B0%E6%8D%AE">3.寻找最近邻数据</a></li>
<li><a href="#4%E5%86%B3%E7%AD%96%E5%88%86%E7%B1%BB">4.决策分类</a></li>
</ul>
</li>
<li><a href="#%E5%9B%9B-python%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0">四、python代码实现</a></li>
</ul>

              </div>
            </div>
          </article>
        </div>

        
          <div class="next-post">
            <div class="next">下一篇</div>
            <a href="https://JIANG-HS.github.io/post/Wj5XKIGfu/">
              <h3 class="post-title">
                梯度下降及线性回归
              </h3>
            </a>
          </div>
        

        
          
            <link rel="stylesheet" href="https://unpkg.com/gitalk/dist/gitalk.css">
<script src="https://unpkg.com/gitalk/dist/gitalk.min.js"></script>

<div id="gitalk-container"></div>

<script>

  var gitalk = new Gitalk({
    clientID: '',
    clientSecret: '',
    repo: '',
    owner: '',
    admin: [''],
    id: (location.pathname).substring(0, 49),      // Ensure uniqueness and length less than 50
    distractionFreeMode: false  // Facebook-like distraction free mode
  })

  gitalk.render('gitalk-container')

</script>

          

          
        

        <div class="site-footer">
  Powered by <a href="https://github.com/getgridea/gridea" target="_blank">Gridea</a>
  <a class="rss" href="https://JIANG-HS.github.io/atom.xml" target="_blank">
    <i class="ri-rss-line"></i> RSS
  </a>
</div>

      </div>
    </div>

    <script>
      hljs.initHighlightingOnLoad()

      let mainNavLinks = document.querySelectorAll(".markdownIt-TOC a");

      // This should probably be throttled.
      // Especially because it triggers during smooth scrolling.
      // https://lodash.com/docs/4.17.10#throttle
      // You could do like...
      // window.addEventListener("scroll", () => {
      //    _.throttle(doThatStuff, 100);
      // });
      // Only not doing it here to keep this Pen dependency-free.

      window.addEventListener("scroll", event => {
        let fromTop = window.scrollY;

        mainNavLinks.forEach((link, index) => {
          let section = document.getElementById(decodeURI(link.hash).substring(1));
          let nextSection = null
          if (mainNavLinks[index + 1]) {
            nextSection = document.getElementById(decodeURI(mainNavLinks[index + 1].hash).substring(1));
          }
          if (section.offsetTop <= fromTop) {
            if (nextSection) {
              if (nextSection.offsetTop > fromTop) {
                link.classList.add("current");
              } else {
                link.classList.remove("current");    
              }
            } else {
              link.classList.add("current");
            }
          } else {
            link.classList.remove("current");
          }
        });
      });

    </script>
  </body>
</html>
